#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def jump(self, A):
        # return self.jump_rec(A)
        # return self.jump_non_rec(A)
        return self.jump_loop(A)

    def jump_loop(self, A):
        # 最快
        start = end = jumps = 0
        l = len(A)

        while end < l-1:
            jumps += 1
            save_farthest = farthest = end      # 最远能到多远

            for stone_idx in range(start, end+1):
                # 计算start 到end之间的那些石头最远能跳多远.
                farthest = max(A[stone_idx] + stone_idx, farthest)

            # 如果最远还在原地: 无法跳到后面了, 直接返回-1
            if farthest == save_farthest:
                return -1

            start = end + 1
            end = farthest
        return jumps


    # =================== non rec  =====================
    def jump_non_rec(self, A):
        # 比较慢
        self.size = len(A)
        self.farthest = self.size * [None]        # 到达index所在最快需要几步?
        self.farthest[0] = 0
        self.A = A

        for i in range(1, self.size):
            self.farthest[i] = self.calc_farthest(i)
            if self.farthest[i] == self.size + 1:
                return -1

        return self.farthest[-1]

    def calc_farthest(self, idx):
        ret = self.size + 1
        for i in range(0, idx):
            if self.A[i] + i >= idx:
                ret = min(self.farthest[i] + 1, ret)

        return ret

    # =================== rec  =====================
    def jump_rec(self, A):
        # 比较慢
        self.need_record = len(A) * [None]     # 表示 第i个元素是否能跳到终点(最终会求出是否所有的节点都能到达终点)
        self.need_record[-1] = 0              # 最后一个元素只用跳0次(本身就在终点位置)

        self.A = A
        self.len = len(A)
        return self.jump_cnt_rec(0)

    def jump_cnt_rec(self, idx):
        # dynamic programming
        if self.need_record[idx] is not None:
            return self.need_record[idx]

        max_jumps = self.A[idx]
        if max_jumps + idx >= self.len-1:
            need = 1
            # print('one step %s' % idx)
        elif max_jumps == 0:
            need = self.len     # 表示不可能的最大值(某个索引只能跳0步, 并且不是最后一个)
        else:
            need = min(
                [self.jump_cnt_rec(idx+l) for l in range(max_jumps, 0, -1)]
            ) + 1

        self.need_record[idx] = need
        return need


def main():
    print("start main")

    s = Solution()
    ret = s.jump(A = [3,2,1,0,4])
    # ret = s.jump(A = [2,3,1,1,4])
    print(ret)

if __name__ == "__main__":
    main()
